package Tree;

import java.util.*;

public class _834_SumofDistancesinTree {
    //solution 1:Dijkstra Algorithm
    /*public int[] sumOfDistancesInTree(int N, int[][] edges) {
        int distance[][] = new int[N][N];
        int[] res = new int[N];
        for (int[] edge:edges) {
            distance[edge[0]][edge[1]] = 1;
            distance[edge[1]][edge[0]] = 1;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (distance[i][j] != 0) {
                    for (int k = 0; k < N; k++) {
                        if (distance[k][j] == 0 && distance[k][i] != 0) {
                            distance[k][j] = distance[i][j] + distance[k][i];
                            distance[j][k] = distance[k][j];
                        }
                    }
                }
            }
        }
        //sum every node's distance
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res[i] += distance[i][j];
            }
        }
        return res;
    }*/
    int[] ans,count;
    List<Set<Integer>> graph;
    int N;
    public int[] sumOfDistancesInTree(int N, int[][] edges) {
        this.N = N;
        graph = new ArrayList<Set<Integer>>();
        ans = new int[N];
        count = new int[N];
        Arrays.fill(count, 1);
        for (int i = 0; i < N; i++) {
            graph.add(new HashSet<Integer>());
            for (int[] edge : edges) {
                graph.get(edge[0]).add(edge[1]);
                graph.get(edge[1]).add(edge[0]);
            }
        }
        dfs(0, -1);
        dfs2(0, -1);
        return ans;
    }

    public void dfs(int node, int parent) {
        for (int child : graph.get(node)) {
            if (child != parent) {
                dfs(child, node);
                count[node] += count[child];
                ans[node] += ans[child] + count[child];
            }
        }
    }

    public void dfs2(int node, int parent) {
        for (int child : graph.get(node)) {
            if (child != parent) {
                ans[child] = ans[node] - count[child] + N - count[child];
                dfs2(child, node);
            }
        }
    }
}
